Date: Wed, 11 Dec 1996 22:33:49 GMT
Server: NCSA/1.5
Content-type: text/html
Last-modified: Fri, 08 Nov 1996 21:54:14 GMT
Content-length: 7570

<HTML>

<HEAD>
<TITLE>CS 302 Section 70 Lecture Notes - Week 10</TITLE>
</HEAD>

<BODY>

<H2><!WA0><!WA0><!WA0><A HREF="http://www.cs.wisc.edu/~tick/cs302.html#text" ><!WA1><!WA1><!WA1><IMG SRC="http://www.cs.wisc.edu/~tick/icons/arrowleft.gif" WIDTH=15 HEIGHT=15></A> Lecture Notes - Week 10,part 1</H2>

<HR>

<DL>
   <DT>Topic:
   <DD>Heaps

   <DT>Text:
   <DD>None.

   <DT>Notes:
   <DD>

   <HR>
   <DT><H4>Heaps:</H4> 
   <DD>Remember that we've seen binary search represented as a tree, i.e.<p>
<pre>
1 3 5 6 8 9 11

becomes

    6 
   / \
  3   9
 / \ / \
1  5 8  11
</pre><p>
Where the middle of the search starts with 6. Then if we need to search the
left part of the list, the new middle is 3; if we need to search the right part,
though, the middle is 9, and so on down the tree. This is one way that an
array can represent a tree.<p>

However, there is another type of tree with an array can represent, called
a heap. There are two things required in order for a tree to be a heap:
<OL>
<LI>It must be a complete tree...Every node must have two children except
for the last one, which can have one or two...so the unique complete binary
trees of size 1 through 7 look like<p>
<pre>
o     o    o        o        o        o        o
     /    / \      / \      / \      / \      / \
    o    o   o    o   o    o   o    o   o    o   o
	         /        / \      / \ /    / \ / \
                o        o   o    o  o o   o  o o  o 
</pre><p>
<LI>All nodes must satisfy the HEAP PROPERTY [Dramatic Chord]: For each node
in a heap, the value of that node must be >= the value of both children, so<p>
<pre>
   8
  / \  
 4   2
</pre><p>
is a heap, whereas<p>
<pre>
   4
  / \
 2   8
</pre><p>
is not.
</OL><p>

How are heaps represented by arrays? Elements of a heap are read left-to-right,
top-to-bottom. So<p>
<pre>
      8
     / \
    6   4 
   / \ / \
  3  5 2  1

is stored as

8 6 4 3 5 2 1
(I'll be referring to this array as LIST from now on)
</pre><p>
<DT><H4>Getting around a heap</H4>  
<DD>Eventually we'll need to talk about how to obtain a sorted list from a
heap. First, though, we need to talk about a few important functions to
help us move around a heap and change a few values inside.<p>
<LI><STRONG>Finding related nodes:</STRONG>Note that LIST(1) = 8. Its left child
is found at LIST(2). LIST(3) is 4. It's left child is at LIST(6). In
general, given an element N,
<UL>
<LI>The left child of LIST(N) is LIST(2*N).
<LI>The right child of LIST(N) is LIST(2*N+1)
<LI>The  parent of LIST(N) is LIST(N/2) (the inverse of finding a child)
</UL><p>
<LI><STRONG>Heapify:</STRONG> Every once in a while, CS invents a word.
The purpose of Heapify ties in to the fact that not every complete binary 
tree is a heap. We have to worry about whether the heap property is satisfied.
Heapify takes a node and moves it down the tree until that node satifies
the heap property (if it was okay to begin with, it won't be moved at all).<p>
<pre>
    2 
   / \
  6   4 
 / \ / \
3  5 8  1

2 6 4 3 5 8 1

Suppose we wanted to Heapify node 1 (LIST(1)=2).
</pre><p> 
2 < 6, so clearly the heap propert is violated. Also, 2 < 4.
So we want to move the node down in the tree. So we switch 6 and 2:
<pre>
    6 
   / \
  2   4
 / \ / \
3  5 8  1

6 2 4 3 5 8 1
</pre>
We chose 6 because 6 > 4 (if we chose 4, 4 would be at the top with 6 as
one of its children, so the heap property would still fail at node 1.<p>
We continue to follow the 2, now located at LIST(2). The heap property still
fails there, so we need to switch the 2 and the 5. We get<p>
<pre>
     6
    / \
   5   4
  / \ / \
 3  2 8  1 

6 5 4 3 2 8 1
</pre><p>
Note that this is still not a heap (the 8 is a problem), but all nodes on the
path from where the 2 was to where the 2 is now satisfy the heap property.<p>
<LI><STRONG>BuildHeap:</STRONG>We have a way of providing the heap property
to a path in the tree; now we need to be able to do it to all paths (once it's
true for all paths, then our tree will be a heap).<p> 
What we're essentially going to do is call heapify within a DO loop. We
won't need to call Heapify on the bottom nodes (usually called Leaf nodes);
Those nodes have no children, so they're as far down as they can go.<p>
<OL>
<LI>Start with the the last node that has children (LIST(3), in our example
above). In general, if the heap has N elements, this node will be LIST(N/2).  
<LI>Heapify that node. Then Heapify the node before that in the list (LIST(2)).
<LI>Repeat until you reach the top of the tree (LIST(1)).<p>  
</OL>
Example:<p>
<pre>
    2
   / \
  4   6
 / \ / \
1  7 3  8
-----------------------------
Heapify Node 3 (the 6)   

    2
   / \
  4   8
 / \ / \
1  7 3  6

6 < 8, so we had to Heapify, and we chose 8 because 

	    8
8 > 3. So  / \   is a heap.
          3   6
-----------------------------
Heapify Node 2 (the 4)

    2
   / \
  7   8
 / \ / \
1  4 3  6

     7
So  / \   is a heap.
   1   4 
-----------------------------
Heapify Node 1 (the 2)
This ecompasses 2 moves...2 gets switched with
the 8, then with the 6).

     8 
    / \
   7   6 
  / \ / \ 
 1  4 3  2
-----------------------------
</pre><p>
Why start with N/2 and work backwards? Suppose we're given Heaps H1,H2 and a
and a node X; the tree<p>
<pre>
        X
       / \
      H1  H2
</pre><p>
can only violate the heap property at one place...X. So if we switch
X with the top of H1, then X is fine, H2 is fine, but H1 may not be
fine. So, let's look at H1.....<p>
<pre>
                X
H1 now =       / \
             H3  H4  
(H3 and H4 are subheaps)
</pre><p>
We're back to the same argument we just had above...If X violates the
heap property, move in down into H3 or H4. This is exactly what Heapify
does.<p>
So the only node to violate the heap property will always be X. Once heapify
finds the right spot for X, then even X isn't a problem, so all nodes are
fine, and we have our heap.<p>
This is why we work back from N/2 to 1. We build heaps out of the lower
parts of the tree, then use them to build a heap out of higher parts of
the tree. In our example, we made a heap out of the tree starting with 
LIST(3), then a heap out of the tree starting at LIST(2). We then used those
two subheaps to build a heap out of the tree starting with LIST(1).<p>
<LI><STRONG>HeapSort:</STRONG> Heaps by themselves don't give us a completely
sorted array, but they give us a quick method for doing so. Consider the 
following heap:<p>
<pre>
     8
    / \
   4   7
  / \ / \
 3  1 2  5

8 4 7 3 1 2 5
</pre>
<OL>
<LI>Take the last element in the array and switch it with the first element. We
now have the largest element in the array at the end of LIST.
<LI>Decrease your heap size. So LIST(1) to LIST(7) is the heap; LIST(8)
is ignored. Since we've already found the largest number, we don't want to
include it in our Heap anymore.<p>
<LI>Heapify LIST(1). We'll get a new Heap based on the first 7 elements of
LIST.<p>
<pre>
     7
    / \
   4   5
  / \ /
 3  1 2

7 4 5 3 1 2 8
</pre><p>
<LI>Repeat these steps until your heap is empty.<p>
<pre>
so the next time thru, for example, switch 2 and
7, decrease your heap size by 1, and Heapify the top. 

     5
    / \
   4   2
  / \
 3   1

5 4 2 3 1 7 8
</pre><p>

So now the 2 largest elements are in order, at the back of the list. So
when you're done, you'll have the entire list is sorted order.     
</OL><p>
</DL>

</BODY>

<HR>

<ADDRESS>
<H5>Copyright &copy 1996<!WA2><!WA2><!WA2><A HREF="http://www.cs.wisc.edu/~tick/tick.html">Jeff Lampert</A> (<!WA3><!WA3><!WA3><A HREF="mailto:tick@cs.wisc.edu">tick@cs.wisc.edu</A>).  Last modified November 8, 1996
</ADDRESS>

</HTML>










